package 算法.leetcode.labuladong.二叉树;

import 算法.leetcode.offer.base.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author lchenglong
 * @date 2022/6/24
 */
public class 在每个树行中找最大值 {
    class Solution {
        public List<Integer> largestValues(TreeNode root) {
            if (root == null) return new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            List<Integer> ans = new ArrayList<>();
            while (!queue.isEmpty()){
                int size = queue.size();
                int max = Integer.MIN_VALUE;
                for (int i=0;i<size;i++) {
                    TreeNode node = queue.poll();
                    max = Math.max(max,node.val);
                    if (node.left != null)
                        queue.add(node.left);
                    if (node.right != null)
                        queue.add(node.right);
                }
                ans.add(max);
            }
            return ans;
        }
    }
}
